package array;

import java.util.*;
import java.util.stream.IntStream;

/**
 * @author lj
 * @date 2022/01/12 16:37
 * @email milolj@foxmail.com
 */
public class LeetCode_array6 {
    /**
     * 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
     * 输出：[2,2]
     * 示例 2:
     * <p>
     * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
     * 输出：[4,9]
     *  
     * <p>
     * 提示：
     * <p>
     * 1 <= nums1.length, nums2.length <= 1000
     * 0 <= nums1[i], nums2[i] <= 1000
     *  
     * <p>
     * 进阶：
     * <p>
     * 如果给定的数组已经排好序呢？你将如何优化你的算法？
     * 如果 nums1 的大小比 nums2 小，哪种方法更优？
     * 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2y0c2/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    /**
     *                        执行结果：
     *                        通过
     *                        显示详情
     *                        执行用时：
     *                        16 ms
     *                        , 在所有 Java 提交中击败了
     *                        5.62%
     *                        的用户
     *                        内存消耗：
     *                        40.8 MB
     *                        , 在所有 Java 提交中击败了
     *                        5.17%
     *                        的用户
     *                        通过测试用例：
     *                        56 / 56
     * @param args
     */

    public static void main(String[] args) {
//        int[] array1 = new int[]{13,19,92};
//        int[] array2 = new int[]{13};
        int[] array1 = new int[]{43,85,49,2,83,2,39,99,15,70,39,27,71,3,88,5,19,5,68,34,7,41,84,2,13,85,12,54,7,9,13,19,92};
        int[] array2 = new int[]{10,8,53,63,58,83,26,10,58,3,61,56,55,38,81,29,69,55,86,23,91,44,9,98,41,48,41,16,42,72,6,4,2,81,42,84,4,13};
        LeetCode_array6 leetCode_array1 = new LeetCode_array6();
        long currentTimeMillis1 = System.currentTimeMillis();
        System.out.println("当前时间是：" + currentTimeMillis1);
        int[] intersect = leetCode_array1.intersect(array1, array2);
        System.out.println("小号的时间是：" + (System.currentTimeMillis() - currentTimeMillis1));
        System.out.println("结果是" + Arrays.toString(intersect));
    }

    /*public int[] intersect(int[] nums1, int[] nums2) {
        Map<Object, Object> map = new HashMap<>();
        Map<Object, Object> temp = new HashMap<>();
        List<Integer> result = new ArrayList<>();

        if (nums1.length > nums2.length) {
            for (int i = 0; i < nums2.length; i++) {
                for (int j = 0; j < nums1.length; j++) {
                    if(nums2[i]==nums1[j] && map.get(nums2[i]) == null) {
                        map.put(nums2[i],1);
                        temp.put(nums2[i]+""+j,j);
                        break;
                    }
                    if (nums2[i]==nums1[j] && map.get(nums2[i]) != null) {
                        if (temp.get(nums2[i]+""+j) != null && temp.get(nums2[i]+""+j).equals(j)) {
                            continue;
                        }
                            map.put(nums2[i],(int)map.get(nums2[i]) + 1);
                        temp.put(nums2[i]+j+"",j);
                            break;
                    }
                }
            }
        } else {
            for (int i = 0; i < nums1.length; i++) {
                for (int j = 0; j < nums2.length; j++) {
                    if(nums1[i]==nums2[j] && map.get(nums1[i]) == null) {
                        map.put(nums1[i],1);
                        temp.put(nums1[i]+""+j,j);
                        break;
                    }
                    if (nums1[i]==nums2[j] && map.get(nums1[i]) != null) {
                        if (temp.get(nums1[i]+""+j) != null && temp.get(nums1[i]+""+j).equals(j)) {
                            continue;
                        }
                        map.put(nums1[i],(int)map.get(nums1[i]) + 1);
                        temp.put(nums1[i]+""+j,j);
                        break;
                    }
                }
            }

        }
        for (Map.Entry<Object, Object> entry : map.entrySet()) {
            int value = (int) entry.getValue();
            for (int i = 0; i < value; i++) {
                result.add((int)entry.getKey());
            }
        }
        int [] end = new int[result.size()];
        for (int i = 0; i < end.length; i++) {
            end[i] = result.get(i);
        }
        return end;
    }*/
    public int[] intersect(int[] nums1, int[] nums2) {
        int length1 = 0;
        int length2 = 0;
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        ArrayList<Integer> list = new ArrayList();
        while (length1 < nums1.length && length2 < nums2.length) {
            if(nums1[length1] == nums2[length2]) {
                list.add(nums1[length1]);
                length1 ++;
                length2 ++;
            } else {
                if (nums1[length1] > nums2[length2]) {
                    length2 ++;
                }else {
                    length1 ++;
                }
            }
        }
        int [] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

}
